Пребројавање комбинације битова

Написати програм који за дати неозначен цео број \(a\) и стринг \(s\) одређује колико пута се комбинација битова наведена у стрингу \(s\) појављује у 64-битном бинарном запису броја \(a\). Преклапања појединих појављивања комбинације су дозвољена.

Улаз

У првој линији стандардног улаза се налази неозначен цео број \(a\), мањи од \(2^{64}\). У другој линији низ од највише 64 бинарне цифре, без размака.

Излаз

На стандардни излаз исписати један цео број, тражени број појављивања.

Пример 1

Улаз

181
101

Излаз

3

Објашњење

Бинарни запис броја 181 је

0000000000000000000000000000000000000000000000000000000010110101

а у овом запису се комбинација битова 101 појављује три пута.

Пример 2

Улаз

181
0101

Излаз

2

Пример 3

Улаз

181
00

Излаз

55